# Definition for a binary tree node.
class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


class Solution(object):
    def countNodes(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        if not root:
            return 0
        h = self.help1(root, 1)
        z = self.help(root, 1, h)
        return z

    def help(self, node, level, h):
        if level == h:
            return 1
        if self.help1(node.right, level + 1) == h:
            s = 1 << (h - level)
            return ((1 << (h - level)) + self.help(node.right, level + 1, h))
        else:
            s1 = 1 << (h - level - 1)
            return ((1 << (h - level - 1)) + self.help(node.left, level + 1, h))

    def help1(self, node, l):
        while node:
            l += 1
            node = node.left
        return l - 1

node1 = TreeNode(1)
node2 = TreeNode(2)
node3 = TreeNode(3)
node4 = TreeNode(4)
node5 = TreeNode(5)
node6 = TreeNode(6)

node1.left = node2
node1.right = node3
node2.left = node4
node2.right = node5
node3.left = node6

s=Solution()
print(s.countNodes(node1))